/************************************************************************
                                                                     
   Xceed Ultimate ListBox for Silverlight                                                                                                                                            
   Copyright (C) 2010 Xceed Software Inc.    
                                                                     
   This program is provided to you under the terms of the GNU General Public  
   License version 2 as published by the Free Software Foundation. 
        
   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY, without even the implied warranty of 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along 
   with this program, if not, write to the Free Software Foundation, Inc., 
   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

   This program can be provided to you by Xceed Software Inc. under a
   proprietary commercial license agreement for use in non-Open Source
   projects. Visit Xceed.com to find the commercial edition of 
   Xceed Ultimate ListBox for Silverlight.                                    
                                                                      
 **********************************************************************/

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;

namespace Xceed.Silverlight.Data
{
  internal class SortPositionFinderEnumerator<T> : AsyncParentEnumerator<T> where T : RawDataItem
  {
    #region Static Fields

    private const long UnknownSize = 1000;

    private static readonly Guid JumpMoveAndFetchCallId = DataUtils.CreateCallId();
    private static readonly Guid GetDataSourceSizeCallId = DataUtils.CreateCallId();
    private static readonly Guid EstimateDataSourceSizeCallId = DataUtils.CreateCallId();
    private static readonly Guid FindPositionCallId = DataUtils.CreateCallId();
    private static readonly Guid BinarySearchCallId = DataUtils.CreateCallId();

    #endregion Static Fields


    internal SortPositionFinderEnumerator( 
      IAsyncEnumerator childEnumerator,
      DataSourceProvider provider,
      IDataHelper dataHelper )
      : base( childEnumerator )
    {
      if( provider == null )
        throw new ArgumentNullException( "provider" );

      if( dataHelper == null )
        throw new ArgumentNullException( "dataHelper" );

      m_provider = provider;
      m_dataHelper = dataHelper;
    }


    public override JumpMoveAndFetchAsyncResult BeginJumpMoveAndFetch( 
      JumpMoveAndFetchParameters parameters, 
      AsyncCallback callback, 
      object state )
    {
      this.CheckMoveAndFetchParameters( parameters.ExpectedMoveCount, parameters.ExpectedFetchCount );

      JumpMoveAndFetchAsyncResult asyncResult = new JumpMoveAndFetchAsyncResult(
                                                  SortPositionFinderEnumerator<T>.JumpMoveAndFetchCallId,
                                                  callback,
                                                  state,
                                                  parameters );

      if( !this.HandleSortPosition( asyncResult, parameters ) )
      {
        // This anonymous method calls the underlying enumerator.
        Func<AsyncCallback, object, IAsyncResult> beginJumpMoveAndFetch =
          ( cb, st ) => base.BeginJumpMoveAndFetch( parameters, cb, st );

        // This anonymous method gets the result from the underlying enumerator.
        Func<AsyncResult, IAsyncResult, DependentCallResult> endJumpMoveAndFetch =
          ( par, iar ) => new DependentCallResult( base.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )iar ) );

        asyncResult.Start( beginJumpMoveAndFetch, endJumpMoveAndFetch );
      }

      return asyncResult;
    }

    public override JumpMoveAndFetchResult<T> EndJumpMoveAndFetch( 
      JumpMoveAndFetchAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.JumpMoveAndFetchCallId );

      return asyncResult.GetCallResult<JumpMoveAndFetchResult<T>>();
    }

    protected override void Dispose( bool disposing )
    {
      m_disposed = true;

      base.Dispose( disposing );
    }

    private bool HandleSortPosition(
      JumpMoveAndFetchAsyncResult asyncResult,
      JumpMoveAndFetchParameters parameters )
    {
      // There is nothing to handle here if the position isn't a SortPosition.
      SortPosition sortPosition = parameters.SourcePosition as SortPosition;
      if( sortPosition == null )
        return false;

      // There is nothing to handle here if the DataSourceProvider is already able
      // to do the job itself.
      IEnumerable<SortDescription> sortedProperties = sortPosition.SortingReference.Take( sortPosition.SortValues.Count );
      if( m_provider.CanJumpTo( sortedProperties ) )
        return false;

      bool isNavigationFilterSupported = NavigationFilterUtils.IsSupported( m_provider, sortPosition.SortingReference );
      bool isPrimaryKeyVolatile = m_provider.IsPrimaryKeyVolatile;

      // There is nothing to handle here if the SortPosition may be replaced by a 
      // FilterExpression that will produce the same result without any impact 
      // on the primary key value of the items.
      if( ( isNavigationFilterSupported ) && ( !isPrimaryKeyVolatile ) )
        return false;

      // The DataSourceProvider must support skipping if we want our search algorithm
      // to be efficient.
      if( !m_provider.CanSkip )
        throw new InvalidOperationException( "An attempt was made to use a DataSourceProvider that does not support skipping." );

      List<string> sortedPropertyNames = sortedProperties.Select( ( item ) => item.PropertyName ).Distinct().ToList();
      bool isTargetingAnItem = ( from pk in m_provider.PrimaryKeyInfo
                                 select sortedPropertyNames.Contains( pk.PropertyName ) ).All( ( result ) => result );
      bool isQueryingForward = DataUtils.IsQueryingForward( parameters.ExpectedMoveCount, parameters.ExpectedFetchCount );

      // Before looking for the position, evaluate the data source size
      // to bound the search.
      asyncResult.AddDependentCall(
        ( cb, st ) => this.BeginGetDataSourceSize( cb, st ),
        ( par, iar ) => new DependentCallResult( this.EndGetDataSourceSize( iar ) ) );

      // Search for the index of the target position in the data source.
      asyncResult.AddDependentCall(
        ( cb, st ) => this.BeginFindPosition( sortPosition, isTargetingAnItem, isQueryingForward, ( long )st, cb, st ),
        ( par, iar ) =>
        {
          long position = this.EndFindPosition( iar );

          if( m_disposed )
            return new DependentCallResult( null );

          return this.HandleSortPositionResult( parameters, position );
        } );

      asyncResult.Start();

      return true;
    }

    private IAsyncResult BeginGetDataSourceSize( AsyncCallback callback, object state )
    {
      AsyncResult asyncResult = new AsyncResult(
                                  SortPositionFinderEnumerator<T>.GetDataSourceSizeCallId,
                                  callback,
                                  state );

      // These anonymous methods try to get the data source size from a data query.
      Func<AsyncCallback, object, IAsyncResult> beginGetDataSourceSize = this.BeginEstimateDataSourceSize;
      Func<AsyncResult, IAsyncResult, DependentCallResult> endGetDataSourceSize =
        ( par, iar ) => new DependentCallResult( this.EndEstimateDataSourceSize( iar ) );

      if( m_provider.CanCount )
      {
        // These anonymous methods try to get the data source size from a count query.
        Func<AsyncCallback, object, IAsyncResult> beginGetDataSourceSizeFromCountQuery =
          ( cb, st ) => this.BeginCount( new CountParameters(), cb, st );
        Func<AsyncResult, IAsyncResult, DependentCallResult> endGetDataSourceSizeFromCountQuery =
          ( par, iar ) =>
          {
            CountResult countResult = this.EndCount( iar );

            if( ( countResult != null ) && ( countResult.Count != null ) )
              return new DependentCallResult( countResult.Count.Value );

            if( m_disposed )
              return new DependentCallResult( null );

            return new DependentCallResult(
                      null,
                      beginGetDataSourceSize,
                      endGetDataSourceSize );
          };

        asyncResult.Start(
          beginGetDataSourceSizeFromCountQuery,
          endGetDataSourceSizeFromCountQuery );
      }
      else
      {
        asyncResult.Start(
          beginGetDataSourceSize,
          endGetDataSourceSize );
      }

      return asyncResult;
    }

    private long EndGetDataSourceSize( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.GetDataSourceSizeCallId );

      if( m_disposed )
        return 0;

      return asyncResult.GetCallResult<long>();
    }

    private IAsyncResult BeginEstimateDataSourceSize( AsyncCallback callback, object state )
    {
      AsyncResult asyncResult = new AsyncResult(
                                  SortPositionFinderEnumerator<T>.EstimateDataSourceSizeCallId,
                                  callback,
                                  state );

      Debug.Assert( SortPositionFinderEnumerator<T>.UnknownSize > 0 );

      long position = SortPositionFinderEnumerator<T>.UnknownSize;

      Func<AsyncCallback, object, IAsyncResult> beginTestDataSourceSize = null;
      beginTestDataSourceSize =
        ( cb, st ) =>
        {
          JumpMoveAndFetchParameters parameters = new JumpMoveAndFetchParameters(
                                                    SourcePosition.BeforeFirst,
                                                    position,
                                                    0,
                                                    false );

          return base.BeginJumpMoveAndFetch( parameters, cb, st );
        };

      Func<AsyncResult, IAsyncResult, DependentCallResult> endTestDataSourceSize = null;
      endTestDataSourceSize =
        ( par, iar ) =>
        {
          JumpMoveAndFetchResult<T> result = base.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )iar );

          if( ( result != null ) && ( result.TotalCount != null ) )
            return new DependentCallResult( result.TotalCount.Value );

          if( m_disposed || !result.Result )
            return new DependentCallResult( position );

          try
          {
            checked
            {
              position *= 2;
            }
          }
          catch( OverflowException )
          {
            return new DependentCallResult( long.MaxValue );
          }

          return new DependentCallResult(
                   null,
                   beginTestDataSourceSize,
                   endTestDataSourceSize );
        };

      asyncResult.Start( beginTestDataSourceSize, endTestDataSourceSize );

      return asyncResult;
    }

    private long EndEstimateDataSourceSize( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.EstimateDataSourceSizeCallId );

      return asyncResult.GetCallResult<long>();
    }

    private IAsyncResult BeginFindPosition( 
      SortPosition targetPosition, 
      bool isTargetingAnItem,
      bool isQueryingForward, 
      long dataSourceSize,
      AsyncCallback callback, 
      object state )
    {
      AsyncResult asyncResult = new AsyncResult(
                                  SortPositionFinderEnumerator<T>.FindPositionCallId,
                                  callback,
                                  state );

      if( ( !m_disposed ) && ( dataSourceSize > 0 ) )
      {
        asyncResult.Start(
          ( cb, st ) => this.BeginBinarySearch( targetPosition, isTargetingAnItem, isQueryingForward, 1, dataSourceSize, cb, st ),
          ( par, iar ) => new DependentCallResult( this.EndBinarySearch( iar ) ) );
      }
      else
      {
        asyncResult.StartSync( 0 );
      }

      return asyncResult;
    }

    private long EndFindPosition( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.FindPositionCallId );

      return asyncResult.GetCallResult<long>();
    }

    private IAsyncResult BeginBinarySearch(
      SortPosition targetPosition,
      bool isTargetingAnItem,
      bool isQueryingForward,
      long lowerBound,
      long upperBound,
      AsyncCallback callback,
      object state )
    {
      Debug.Assert( lowerBound <= upperBound );

      AsyncResult asyncResult = new AsyncResult(
                                  SortPositionFinderEnumerator<T>.BinarySearchCallId,
                                  callback,
                                  state );
      long center = 0;

      // These anonymous methods do a binary search possibly asynchronously.
      // The algorithm may fail when the calls are asynchronous and the
      // data source changes while searching.
      Func<AsyncCallback, object, IAsyncResult> beginSearch = null;
      beginSearch =
        ( cb, st ) =>
        {
          center = lowerBound + ( upperBound - lowerBound ) / 2;

          JumpMoveAndFetchParameters parameters = new JumpMoveAndFetchParameters(
                                                    SourcePosition.BeforeFirst,
                                                    center,
                                                    0 );

          return base.BeginJumpMoveAndFetch( parameters, cb, st );
        };
      Func<AsyncResult, IAsyncResult, DependentCallResult> endSearch = null;
      endSearch =
        ( par, iar ) =>
        {
          JumpMoveAndFetchResult<T> result = base.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )iar );

          if( m_disposed )
            return new DependentCallResult( 0 );

          SourcePosition endPosition = result.EndPositionObject;
          int compare;

          if( endPosition is ItemPosition )
          {
            T item = ( ( ItemPosition )endPosition ).Item as T;
            compare = m_dataHelper.Compare( targetPosition, item );

            if( ( isTargetingAnItem ) && ( compare != 0 ) )
            {
              SortPosition itemBound = new SortPosition(
                                         targetPosition.SortingReference,
                                         targetPosition.SortValues,
                                         ( targetPosition.StartPosition == StartPosition.Before )
                                           ? StartPosition.After
                                           : StartPosition.Before );

              int compareItemBound = m_dataHelper.Compare( itemBound, item );

              // The item has been found.
              if( compareItemBound != compare )
              {
                compare = 0;
              }
            }

            // The targeted position has been found.
            if( compare == 0 )
            {
              long firstItemOffset = 0;

              // The current item is the one that comes prior to the first desired item.
              // Find out the offset to apply to get to the first item.
              if( ( targetPosition.StartPosition == StartPosition.Before ) != ( isQueryingForward ) )
              {
                firstItemOffset = ( isQueryingForward ) ? 1 : -1;
              }

              return new DependentCallResult( center + firstItemOffset );
            }
          }
          // The target position is before the first item of the data source.
          else if( endPosition.IsBeforeFirst )
          {
            return new DependentCallResult( 0 );
          }
          else if( endPosition.IsAfterLast )
          {
            // The target position is after the last item of the data source.
            if( lowerBound >= upperBound )
              return new DependentCallResult( center );

            compare = 1;
          }
          else
          {
            throw new DataInternalException();
          }

          Debug.Assert( compare != 0 );

          if( compare < 0 )
          {
            upperBound = center - 1;
          }
          else
          {
            lowerBound = center + 1;
          }

          // There is no more item to test.
          if( lowerBound > upperBound )
          {
            long targetBound = ( isQueryingForward )
                                 ? lowerBound
                                 : upperBound;

            return new DependentCallResult( targetBound );
          }
          else
          {
            return new DependentCallResult( null, beginSearch, endSearch );
          }
        };

      asyncResult.Start( beginSearch, endSearch );

      return asyncResult;
    }

    private long EndBinarySearch( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.BinarySearchCallId );

      return asyncResult.GetCallResult<long>();
    }

    private DependentCallResult HandleSortPositionResult(
      JumpMoveAndFetchParameters parameters,
      long targetPosition )
    {
      int fetchCount = parameters.ExpectedFetchCount;
      long moveCount = targetPosition + parameters.ExpectedMoveCount;
      SortPosition targetSortPosition = parameters.SourcePosition as SortPosition;

      // Since a SortPosition swallow one move to get on the next item, we may need
      // to corrected the move counter.
      if( targetSortPosition != null )
      {
        moveCount -= Math.Sign( parameters.ExpectedMoveCount );
      }

      // We cannot start a query that doesn't move or fetch.  We'll have
      // to fetch at least one element.
      if( moveCount == 0 && fetchCount == 0 )
      {
        fetchCount = 1;
      }

      JumpMoveAndFetchParameters newParameters = new JumpMoveAndFetchParameters(
                                                   SourcePosition.BeforeFirst,
                                                   moveCount,
                                                   fetchCount,
                                                   parameters.ApproximateMove );

      // This anonymous method will start the query on the child enumerator.
      Func<AsyncCallback, object, IAsyncResult> beginQuery =
        ( cb, st ) => base.BeginJumpMoveAndFetch( newParameters, cb, st );

      // This anonymous method will convert the result of the query to the initial
      // requested query format.
      Func<AsyncResult, IAsyncResult, DependentCallResult> endQuery =
        ( par, iar ) =>
        {
          JumpMoveAndFetchAsyncResult asyncResult = ( JumpMoveAndFetchAsyncResult )iar;
          JumpMoveAndFetchAsyncResult parentAsyncResult = ( JumpMoveAndFetchAsyncResult )par;
          JumpMoveAndFetchResult<T> completeResult = base.EndJumpMoveAndFetch( asyncResult );

          // The move failed.  We must find out the actual move count.
          Nullable<long> actualMoveCount;
          if( completeResult.FetchedItems == null )
          {
            if( completeResult.ActualMoveCount.HasValue )
            {
              long actualMoveOffset = targetPosition;

              // We must take into account the move that is swallowed by the SortPosition
              // for the actual move count calculation.
              if( targetSortPosition != null )
              {
                if( ( completeResult.ExpectedMoveCount != 0 ) 
                  && ( completeResult.ExpectedMoveCount != completeResult.ActualMoveCount ) )
                {
                  actualMoveOffset -= Math.Sign( completeResult.ExpectedMoveCount );
                }
                // We have to take into account the extra move that got us out of bound.
                else
                {
                  actualMoveOffset -= Math.Sign( parameters.ExpectedMoveCount );
                }
              }

              actualMoveCount = completeResult.ActualMoveCount.Value - actualMoveOffset;
            }
            else
            {
              actualMoveCount = null;
            }
          }
          // The move succeeded.
          else
          {
            actualMoveCount = parentAsyncResult.ExpectedMoveCount;
          }

          // Remove the item fecthed if we had to fake the fetch part.
          ICollection<T> fetchedItems = completeResult.FetchedItems;
          if( ( parentAsyncResult.ExpectedFetchCount != fetchCount )
            && ( fetchedItems != null )
            && ( fetchedItems.Count > 0 ) )
          {
            fetchedItems = new List<T>( 0 );
          }

          return new DependentCallResult(
                   new JumpMoveAndFetchResult<T>(
                     parentAsyncResult,
                     actualMoveCount,
                     fetchedItems,
                     completeResult.Result,
                     completeResult.EndPositionObject,
                     completeResult.EndPositionOffset,
                     completeResult.TotalCount ) );
        };

      return new DependentCallResult( null, beginQuery, endQuery );
    }

    #region Private Fields

    private DataSourceProvider m_provider; //null
    private IDataHelper m_dataHelper; //null
    private bool m_disposed; //false

    #endregion
  }
}
